package com.problem.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 */
public class Problem40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer>       tmp    = new ArrayList<>();
        back(target, result, tmp, candidates, 0);
        return result;
    }

    public void back(int remain, List<List<Integer>> allList, List<Integer> tmp, int[] candidates, int start) {
        if (remain == 0) {
            allList.add(new ArrayList<>(tmp));
            return;
        } else if (remain < 0) {
            return;
        } else {
            for (int i = start; i < candidates.length && candidates[i] <= remain; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                tmp.add(candidates[i]);
                back(remain - candidates[i], allList, tmp, candidates, i + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
